package com.cb2.algorithm.leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/">二叉树的最近公共祖先(Lowest Common Ancestor of a Binary Tree)</a>
 * <p>给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。</p>
 * <p><a href="https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin">最近公共祖先</a>的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
 *                        3
 *                     /    \
 *                    5      1
 *                   / \    / \
 *                  6   2  0  8
 *                     / \
 *                    7   4
 *      输出：3
 *      解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
 *
 * 示例 2：
 *      输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
 *      输出：5
 *      解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
 *
 * 示例 3：
 *      输入：root = [1,2], p = 1, q = 2
 *      输出：1
 *     </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>树中节点数目在范围 [2, 10^5] 内。</li>
 *         <li>-10^9 <= Node.val <= 10^9</li>
 *         <li>所有 Node.val 互不相同 。</li>
 *         <li>p != q</li>
 *         <li>p 和 q 均存在于给定的二叉树中。</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @see LC0235LowestCommonAncestorOfABinarySearchTree_M 二叉搜索树的最近公共祖先(Lowest Common Ancestor of a Binary Search Tree)
 * @see LC0236LowestCommonAncestorOfABinaryTree_M 二叉树的最近公共祖先(Lowest Common Ancestor of a Binary Tree)
 * @see LC1644LowestCommonAncestorOfBinaryTree_II_M 二叉树的最近公共祖先 II(Lowest Common Ancestor of a Binary Tree II)
 * @see LC1650LowestCommonAncestorOfBinaryTree_III_M 二叉树的最近公共祖先 III(Lowest Common Ancestor of a Binary Tree III)
 * @since 2023/10/18 15:25
 */
public class LC0236LowestCommonAncestorOfABinaryTree_M {
    static class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || p == root || q == root) {
                return root;
            }
            // 在左子树上查找最近公共祖先
            TreeNode leftLowestCommonAncestor = lowestCommonAncestor(root.left, p, q);
            // 在右子树上查找最近公共祖先
            TreeNode rightLowestCommonAncestor = lowestCommonAncestor(root.right, p, q);
            if (leftLowestCommonAncestor == null) {
                return rightLowestCommonAncestor;
            }
            if (rightLowestCommonAncestor == null) {
                return leftLowestCommonAncestor;
            }
            // 在左子树和右子树都有公共祖先，那一定是根节点
            return root;
        }

        public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || p == root || q == root) {
                return root;
            }
            Map<Integer, TreeNode> currNode2parentNodeMap = new HashMap<>();
            dfs(root, currNode2parentNodeMap);
            // p节点所有的祖先节点
            Set<TreeNode> pNodeAncestorSet = new HashSet<>();
            while (p != null) {
                pNodeAncestorSet.add(p);
                p = currNode2parentNodeMap.get(p.val);
            }
            while (q != null) {
                if (pNodeAncestorSet.contains(q)) {
                    return q;
                }
                q = currNode2parentNodeMap.get(q.val);
            }
            return null;
        }

        private void dfs(TreeNode root, Map<Integer, TreeNode> currNode2parentNodeMap) {
            if (root == null) {
                return;
            }
            if (root.left != null) {
                currNode2parentNodeMap.put(root.left.val, root);
                dfs(root.left, currNode2parentNodeMap);
            }
            if (root.right != null) {
                currNode2parentNodeMap.put(root.right.val, root);
                dfs(root.right, currNode2parentNodeMap);
            }
        }
    }
}